package com.zjj.lbw.interview.array;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhanglei.zjj
 * @description 两数之和-暴力解法 & 使用map
 * @date 2023/9/1 9:30
 */
public class TwoNumberSum {
    /**
     * 基于暴力解法
     * @param arr
     * @param target
     * @return
     */
    public static int[] twoNumberSumBF(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] + arr[j] == target) {
                    return new int[] {i, j};
                }
            }
        }
        return new int[0];
    }

    /**
     * 引入Map
     * @param arr
     * @param target
     * @return
     */
    public static int[] twoNumberSumUseMap(int[] arr, int target) {
        Map<Integer, Integer> map = new HashMap<>(arr.length);
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(target - arr[i])) {
                return new int[] {map.get(target - arr[i]), i};
            } else {
                map.put(arr[i], i);
            }
        }

        return new int[0];
    }

    /**
     * 基于二分查找
     * @param arr
     * @param target
     * @return
     */
    public static int[] twoNumberSumBinarySearch(int[] arr, int target) {
        int low, high = arr.length - 1;
        for (int i = 0; i < arr.length; i++) {
            low = i;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (arr[mid] == target - arr[i]) {
                    return new int[] {i, mid};
                } else if (arr[mid] > target - arr[i]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
        }

        return new int[0];
    }

    /**
     * 基于双指针
     * @param arr
     * @param target
     * @return
     */
    public static int[] twoNumberSumDoubleIndex(int[] arr, int target) {
        int head = 0, tail = arr.length - 1;
        while (head < tail) {
            if (arr[head] + arr[tail] == target) {
                return new int[] {head, tail};
            } else if (arr[head] + arr[tail] < target) {
                head ++;
            } else {
                tail --;
            }
        }

        return new int[0];
    }
}
